This application includes a microfiche appendix including 2 sheets of microfiche and 163 frames of material.
The present invention relates to the scheduling of transportation resources, and more particularly, to a method for heuristically constructing a schedule.
Transportation scheduling is the process of planning how to move items from one location to another location using a fleet of carriers and under a set of restrictive constraints. One example is demand-response para-transit scheduling. In this example, wheelchair-bound and ambulatory customers make requests by telephone for round trip transportation from home to medical appointments, shopping, community centers, etc. . . . A fleet of vehicles must provide service under a multitude of constraints such as: (1) honoring a requested pick up time, (2) dropping the customer off before, but at most 60 minutes before, the appointment time, (3) and planning for much slower travel speed during rush hours.
Transportation scheduling takes a collection of trip requests as its set of subgoals, and a fleet of vehicles as its resources. The scheduling process constructs a set of manifests, one for each vehicle. A manifest is an ordered sequence of stop events. Each event has an associated location (either pickup or dropoff) and an assigned time.
The set of manifests or schedule must be realistic (known in the art as xe2x80x9cstreetabilityxe2x80x9d), satisfy all domain constraints (known in the art as xe2x80x9ccorrectnessxe2x80x9d), and be of high quality (known in the art as xe2x80x9cgoodnessxe2x80x9d).
Prior art attempts to solve the transportation scheduling problem have been varied and are exemplified by U.S. Pat. Nos. 5,715,165, 5,692,125, 5,623,413, 5,623,404, 5,619,695, 5,177,684, and 4,926,343. Although these prior art attempts have been moderately successful, some of these methods are computationally intensive. Thus, there is still a need for an easily implementable method for transportation scheduling that accurately models the problem and can be operated in real time.
An improved transportation scheduling method for scheduling a plurality of trips T1-Tn using a plurality of vehicles V1-Vn, each of said plurality of vehicles having a trip manifest is disclosed. The method comprises the steps of: (a) generating a usability matrix that determines which of said plurality of vehicles V1-Vn is useable with each of said plurality of trips T1-Tn; (b) determining a best trip of said plurality of trips T1-Tn to be scheduled next; (c) determining a best vehicle from said plurality of vehicles V1-Vn for accommodating said best trip; (d) determining a best insertion pair into said trip manifest of said best vehicle for said best trip and updating said trip manifest to include said best insertion pair; (e) updating said usability matrix to reflect the scheduling of said best trip on said best vehicle; and (f) repeating steps (a)-(e) until all of the trips in said plurality of trips T1-Tn have been scheduled or determined to be unschedulable.